package com.ww.springboot.boot.algorithm.leetcode1;

/**
 * 描述：
 *
 * @author 🧑 ‍wanwei
 * @since 2022-03-30 10:11
 */
public class BH781森林中的兔子 {

    public static void main(String[] args) {
        int[] answers = {10,10,10};
        System.out.println(numRabbits(answers));
    }


    /**
     * 1.找出相同数字 并统计个数
     *
     * 最小可能就是 尽量让回答相互包含
     * 比如 回答5的有6个 则假设这6个全部参与回答 则回答5的6个数 表示的最小数字是6
     *  如果回答5的有12个 则假设这12个全部参与回答 则回答5的12个数 表示的最小数字是6*2
     *  如果回答5的有13个 则假设12个全部参与回答,多余一个回答的 还有隐藏的5个没有回答 则回答5的13个数 表示的最小数字是6*2+6
     *
     * @param answers
     * @return
     */
    public static int numRabbits(int[] answers) {
        int max = 0;
        for (int i = 0; i < answers.length; i++) {
            max = Math.max(max, answers[i]);
        }
        int[] nums = new int[max + 1];
        for (int i = 0; i < answers.length; i++) {
            nums[answers[i]]++;
        }

        int total = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                continue;
            }
            int n = nums[i] / (i + 1);
            int m = nums[i] % (i + 1);
            if (m > 0) {
                n++;
            }
            total += n * (i + 1);
        }
        return total;
    }
}
